SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>MM algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">MM algorithm</span></span>

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><p>The <b>MM algorithm</b> is an iterative <a href="Optimization" class="mw-redirect" title="Optimization">optimization</a> method which exploits the <a href="Convex_function" title="Convex function">convexity</a> of a function in order to find its maxima or minima. The MM stands for “Majorize-Minimization” or “Minorize-Maximization”, depending on whether the desired optimization is a minimization or a maximization. Despite the name, MM itself is not an algorithm, but a description of how to construct an <a href="Optimization_algorithm" class="mw-redirect" title="Optimization algorithm">optimization algorithm</a>.

</p><p>The <a href="Expectation%E2%80%93maximization_algorithm" title="Expectation–maximization algorithm">expectation–maximization algorithm</a> can be treated as a special case of the MM algorithm.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

However, in the EM algorithm <a href="Conditional_expectation" title="Conditional expectation">conditional expectations</a> are usually involved, while in the MM algorithm convexity and inequalities are the main focus, and it is easier to understand and apply in most cases.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

<p>The historical basis for the MM algorithm can be dated back to at least 1970, when Ortega and Rheinboldt were performing studies related to <a href="Line_search" title="Line search">line search</a> methods.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> The same concept continued to reappear in different areas in different forms. In 2000, Hunter and Lange put forth "MM" as a general framework.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> Recent studies have applied the method in a wide range of subject areas, such as <a href="Mathematics" title="Mathematics">mathematics</a>, <a href="Statistics" title="Statistics">statistics</a>, <a href="Machine_learning" title="Machine learning">machine learning</a> and <a href="Engineering" title="Engineering">engineering</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2></div>

<p>The MM algorithm works by finding a surrogate function that minorizes or majorizes the objective function. Optimizing the surrogate function will either improve the value of the objective function or leave it unchanged.

</p><p>Taking the minorize-maximization version, let <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(\theta )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(\theta )}</annotation>

</semantics>

</math></span><img src="./205329be9269c44e4efaeb7001fc60bbe5188eaf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.178ex; height:2.843ex;" alt="{\displaystyle f(\theta )}" loading="lazy"></span> be the objective concave function to be maximized. At the <span class="texhtml mvar" style="font-style:italic;">m</span> step of the algorithm, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m=0,1...}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=0,1...}</annotation>

</semantics>

</math></span><img src="./1bf55954093fb1fb761655cda141527bebf5f2a8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.438ex; height:2.509ex;" alt="{\displaystyle m=0,1...}" loading="lazy"></span>, the constructed function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(\theta |\theta _{m})}">

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(\theta |\theta _{m})}</annotation>

</semantics>

</math></span><img src="./daeac9abc1392c355cf48e48dd62632eb6035d08.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.428ex; height:2.843ex;" alt="{\displaystyle g(\theta |\theta _{m})}" loading="lazy"></span> will be called the minorized version of the objective function (the surrogate function) at <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta _{m}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta _{m}}</annotation>

</semantics>

</math></span><img src="./5adaa3619c27da284f8a29b49226b9cd4fd09bdf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.765ex; height:2.509ex;" alt="{\displaystyle \theta _{m}}" loading="lazy"></span> if

</p>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(\theta |\theta _{m})\leq f(\theta ){\text{ for all }}\theta }</annotation>

</semantics>

</math></span><img src="./cdf52548efb3c95ecdac6f28ecb82b360adeb71c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.779ex; height:2.843ex;" alt="{\displaystyle g(\theta |\theta _{m})\leq f(\theta ){\text{ for all }}\theta }" loading="lazy"></span></dd>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(\theta _{m}|\theta _{m})=f(\theta _{m})}</annotation>

</semantics>

</math></span><img src="./443720ffd7a6e8be4dd76e046e2dd9ac049b4a24.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.055ex; height:2.843ex;" alt="{\displaystyle g(\theta _{m}|\theta _{m})=f(\theta _{m})}" loading="lazy"></span></dd></dl>

<p>Then, maximize <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(\theta |\theta _{m})}">

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(\theta |\theta _{m})}</annotation>

</semantics>

</math></span><img src="./daeac9abc1392c355cf48e48dd62632eb6035d08.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.428ex; height:2.843ex;" alt="{\displaystyle g(\theta |\theta _{m})}" loading="lazy"></span> instead of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(\theta )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(\theta )}</annotation>

</semantics>

</math></span><img src="./205329be9269c44e4efaeb7001fc60bbe5188eaf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.178ex; height:2.843ex;" alt="{\displaystyle f(\theta )}" loading="lazy"></span>, and let

</p>

<msub>

</mrow>

</msub>

</mrow>

</munder>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta _{m+1}=\arg \max _{\theta }g(\theta |\theta _{m})}</annotation>

</semantics>

</math></span><img src="./98190eaaad3bf2bdfe915c5a3d21c7fe55e2a81c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:23.729ex; height:4.009ex;" alt="{\displaystyle \theta _{m+1}=\arg \max _{\theta }g(\theta |\theta _{m})}" loading="lazy"></span></dd></dl>

<p>The above iterative method will guarantee that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(\theta _{m})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(\theta _{m})}</annotation>

</semantics>

</math></span><img src="./1eef9fc6a571ca66ecaac3a700fd68849b1cff18.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.853ex; height:2.843ex;" alt="{\displaystyle f(\theta _{m})}" loading="lazy"></span> will converge to a local optimum or a saddle point as <span class="texhtml mvar" style="font-style:italic;">m</span> goes to infinity.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> By the above construction

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(\theta _{m+1})\geq g(\theta _{m+1}|\theta _{m})\geq g(\theta _{m}|\theta _{m})=f(\theta _{m})}</annotation>

</semantics>

</math></span><img src="./17c8b070e63cf719134b504bcf954e7032244e86.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:43.409ex; height:2.843ex;" alt="{\displaystyle f(\theta _{m+1})\geq g(\theta _{m+1}|\theta _{m})\geq g(\theta _{m}|\theta _{m})=f(\theta _{m})}" loading="lazy"></span></dd></dl>

<p>The marching of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta _{m}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta _{m}}</annotation>

</semantics>

</math></span><img src="./5adaa3619c27da284f8a29b49226b9cd4fd09bdf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.765ex; height:2.509ex;" alt="{\displaystyle \theta _{m}}" loading="lazy"></span> and the surrogate functions relative to the objective function is shown in the figure.

</p><p>Majorize-Minimization is the same procedure but with a convex objective to be minimised.

</p>

<div class="mw-heading mw-heading2"><h2 id="Constructing_the_surrogate_function">Constructing the surrogate function</h2></div>

<p>One can use any inequality to construct the desired majorized/minorized version of the objective function. Typical choices include

</p>

<ul><li><a href="Jensen's_inequality" title="Jensen's inequality">Jensen's inequality</a></li>

<li>Convexity inequality</li>

<li><a href="Cauchy%E2%80%93Schwarz_inequality" title="Cauchy–Schwarz inequality">Cauchy–Schwarz inequality</a></li>

<li><a href="Inequality_of_arithmetic_and_geometric_means" class="mw-redirect" title="Inequality of arithmetic and geometric means">Inequality of arithmetic and geometric means</a></li>

<li>Quadratic majorization/mininorization via second order <a href="Taylor_expansion" class="mw-redirect" title="Taylor expansion">Taylor expansion</a> of twice-differentiable functions with bounded curvature.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFLange" class="citation web cs1">Lange, Kenneth. <a rel="nofollow" class="external text" href="http://www.stat.berkeley.edu/~aldous/Colloq/lange-talk.pdf">"The MM Algorithm"</a> <span class="cs1-format">(PDF)</span>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFLange2016" class="citation book cs1">Lange, Kenneth (2016). <i>MM Optimization Algorithms</i>. SIAM. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F1.9781611974409">10.1137/1.9781611974409</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-61197-439-3</bdi>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFLangeZhou2022" class="citation journal cs1">Lange, K.; Zhou, H. (2022). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10191373">"A legacy of EM algorithms"</a>. <i><a href="International_Statistical_Review" class="mw-redirect" title="International Statistical Review">International Statistical Review</a></i>. <b>90</b> (Suppl 1): <span class="nowrap">S52 –</span> <span class="nowrap">S66</span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1111%2Finsr.12526">10.1111/insr.12526</a>. <a href="PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10191373">10191373</a></span>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/37204987">37204987</a>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFOrtegaRheinboldt1970" class="citation book cs1">Ortega, J.M.; Rheinboldt, W.C. (1970). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/iterativesolutio0000orte"><i>Iterative Solutions of Nonlinear Equations in Several Variables</i></a></span>. New York: Academic. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/iterativesolutio0000orte/page/253">253</a>–255. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780898719468</bdi>.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFHunterLange2000" class="citation journal cs1">Hunter, D.R.; Lange, K. (2000). "Quantile Regression via an MM Algorithm". <i><a href="Journal_of_Computational_and_Graphical_Statistics" title="Journal of Computational and Graphical Statistics">Journal of Computational and Graphical Statistics</a></i>. <b>9</b> (1): <span class="nowrap">60–</span>77. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.206.1351">10.1.1.206.1351</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F1390613">10.2307/1390613</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/1390613">1390613</a>.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFWu1983" class="citation journal cs1">Wu, C. F. Jeff (1983). <a rel="nofollow" class="external text" href="https://doi.org/10.1214%2Faos%2F1176346060">"On the Convergence Properties of the EM Algorithm"</a>. <i><a href="Annals_of_Statistics" title="Annals of Statistics">Annals of Statistics</a></i>. <b>11</b> (1): <span class="nowrap">95–</span>103. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1214%2Faos%2F1176346060">10.1214/aos/1176346060</a></span>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2240463">2240463</a>.</cite></span>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-12-13" href="https://en.wikipedia.org/wiki/?title=MM_algorithm&oldid=1262813511">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>